package leetcode;

import java.util.Stack;

/**
 * Leetcode20【有效的括号】
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 */
public class ValidParentheses {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){//当读到的字符为左面的括号时直接入栈
                stack.push(s.charAt(i));
            }else {//当为有括号时
                if (stack.isEmpty()){//为空说明只有右括号肯定false
                    return false;
                }
                char top = stack.pop();//出栈
                if (s.charAt(i) == ')' && top != '('){//查看是否匹配
                    return false;
                }else if (s.charAt(i) == ']' && top != '['){
                    return false;
                }else if (s.charAt(i) == '}' && top != '{'){
                    return false;
                }
            }
        }
        if(!stack.isEmpty()){//当都走完如果栈还不为空说明左括号多了
            return false;
        }else {
            return true;
        }

    }
}
